import javax.swing.tree.TreeNode;
import java.util.List;

//TIP 要<b>运行</b>代码，请按 <shortcut actionId="Run"/> 或
// 点击装订区域中的 <icon src="AllIcons.Actions.Execute"/> 图标。
public class Main {
    /**
     * 求根节点到叶子节点数字之和
     */
    /*public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    public int dfs(TreeNode root, int param) {
        int ret = param * 10 + root.val;
        if(root.left == null && root.right == null) {
            return ret;
        }
        int result = 0;
        if(root.left != null) result += dfs(root.left, ret);
        if(root.right != null) result += dfs(root.right, ret);
        return result;
    }*/


    /**
     * 计算布尔二叉树的值
     * @param root
     * @return
     */
    /*public boolean evaluateTree(TreeNode root) {
        if( root.left == null) {
            return root.val == 1 ? true : false;
        }
        boolean left = evaluateTree(root.left);
        boolean right = evaluateTree(root.right);
        return root.val == 2 ? left | right : right & left;
    }*/


    /**
     * 快速幂
     * @param x
     * @param n
     * @return
     */
    public double myPow(double x, int n) {
        return n < 0 ? 1.0 / pow(x, -n) : pow(x, n);
    }

    public double pow(double x, int n) {
        if (n == 0) {
            return 1.0;
        }
        double tmp = pow(x, n / 2);
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }

    /**
     * 汉诺塔递归
     *
     * @param a
     * @param b
     * @param c
     */
    public void hanota(List<Integer> a, List<Integer> b, List<Integer> c) {
        //递归代码如何来编写呢?步骤详见
        dsf(a, b, c, a.size());
    }

    public void dsf(List<Integer> a, List<Integer> b, List<Integer> c, int n) {
        //1` 根据重复子问题--->函数头
        //2`只关心一个子问题在干什么-->函数体
        //3`细节-->递归出口
        if (n == 1) {
            c.add(a.remove(a.size() - 1));
            return;
        }
        dsf(a, c, b, n - 1);
        c.add(a.remove(a.size() - 1));//此处不是remove(0)---当我们递归往深处走后,
        dsf(b, a, c, n - 1);
    }

    /**
     * 翻转链表
     * @param head
     * @return
     */
//    public ListNode reverseList(ListNode head) {
//        if (head == null || head.next == null )
//            return head;
//        ListNode ret = reverseList(head.next);
//        head.next.next = head;
//        head.next = null;
//        return ret;
//
//    }

    /**
     * 两两交换链表中的节点
     * @param head
     * @return
     */
    /*public ListNode swapPairs(ListNode head) {
        //宏观角度看待递归1
        if(head == null || head.next == null) {
            //递归的开始条件往往也是递归的结束条件 ~~
            return head;
        }
        ListNode newHead = swapPairs(head.next.next);
        head.next.next = head;
        ListNode ret = head.next;
        head.next = newHead;
        return ret;

    }*/






}